package code;

public class Code64 {
	public int minPathSum(int[][] grid){
		int n=grid.length;
		if(n==0)
			return 0;
		int m=grid[0].length;
		int[][] dp=new int[n][m];
		for(int i=0;i<n;i++)
			for(int j=0;j<m;j++){
				if(i==0){
					if(j==0)
						dp[i][j]=grid[i][j];
					else
						dp[i][j]=grid[i][j-1]+grid[i][j];
				}
				else{
					if(j==0){
						dp[i][j]=dp[i-1][j]+grid[i][j];
					}
					else{
						dp[i][j]=grid[i][j];
						if(dp[i-1][j]>dp[i][j-1])
							dp[i][j]+=dp[i][j-1];
						else
							dp[i][j]+=dp[i-1][j];
					}
				}
			}
		return dp[n-1][m-1];
	}
	public static void main(String[] args){
		
	}
}
